package Offer2017;

/**
 * 数组中出现次数超过一半的数字
 * Created by 雷文康 on 2018/1/1.
 */
public class Test29 {
    public static void main(String[] args) {
        int[] array = {3,2,3,3,4,2,6,8,3,3,3};
        System.out.println(moreThanHalfNum(array));
    }
    //基于Partition函数
     public static int moreThanHalfNum(int[] array){
         if (array == null || array.length == 0){
             System.out.println("输入非法！");
             return -1;
         }
         int low = 0;
         int high = array.length - 1;
         int mid = (low + high)/2;
         int pos = partition(array, low, high);
         while (pos != mid) {
             if (pos < mid) {
                 low = pos + 1;
                 pos = partition(array, low, high);
             } else if (pos > mid) {
                 high = pos - 1;
                 pos = partition(array, low, high);
             }
         }
         if (!checkMoreThanHalf(array, array[pos])){
             System.out.println("不存在!");
             return -1;
         }
         return array[pos];
     }


    public static int moreThanHalfNum2(int[] array) {
        if (array == null || array.length == 0) {
            System.out.println("输入非法！");
            return -1;
        }
        int result = array[0];
        int index = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == result) {
                index++;
            } else {
                index--;
                if (index == 0) {
                    result = array[i];
                    index = 1;
                }
            }
        }
        if (!checkMoreThanHalf(array, result)) {
            System.out.println("不存在！");
            return -1;
        }
        return result;
    }





     private static boolean checkMoreThanHalf(int[] array, int num){
         int count = 0;
         for (int i = 0; i < array.length; i++) {
             if (array[i] == num){
                 count++;
             }
         }
         if (2 * count >  array.length) {
             return true;
         }
         return false;
     }

     private static int partition(int[] array, int low, int high){
         int val = array[low];
         while (low < high){
             while (low < high && array[high] >= val) {
                 high--;
             }
             array[low] = array[high];
             while (low < high && array[low] <= val) {
                 low++;
             }
             array[high] = array[low];
         }
         array[low] = val;
         return low;
     }
}
